package twice.class_digui;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
//子序列问题（从左到右要不要）
public class Class02_PrintAllSubsquences {
    public static List<String> subs(String s){
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }

    private static void process1(char[] str, int i, List<String> ans, String path) {
        if(i == str.length){
            ans.add(path);
            return;
        }
        process1(str,i+1,ans,path);
        process1(str, i + 1, ans, path + String.valueOf(str[i]));
    }

    public static List<String> subsNoRepeat(String s) {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, path);
        List<String> ans = new ArrayList<>();
        for (String cur : set) {
            ans.add(cur);
        }
        return ans;
    }

    public static void process2(char[] str, int index, HashSet<String> set, String path) {
        if (index == str.length) {
            set.add(path);
            return;
        }
        String no = path;
        process2(str, index + 1, set, no);
        String yes = path + String.valueOf(str[index]);
        process2(str, index + 1, set, yes);
    }


    public static int  numDistinct(String s, String t) {
        String path = "";
        char[] c = s.toCharArray();
        int res = 0;
        List<String> ans = new ArrayList<>();
        process3(c,0,path,t,res);
        return res;
    }
    static void process3(char[] c,int i,String path,String t,int res){
        if(i == c.length){
            if(path.equals(t)){
                res++;
            }
            return;
        }
        process3(c,i+1,path,t,res);
        process3(c,i+1,path+String.valueOf(c[i]),t,res);
    }
    public static void main(String[] args) {
        String test = "rabbbit";
        List<String> ans1 = subs(test);
        List<String> ans2 = subsNoRepeat(test);
        int s = numDistinct("rabbbit","rabbit");
        System.out.println(s);
//        System.out.println("=================");
//        for (String str : ans1) {
//            System.out.println(str);
//        }
//        System.out.println("=================");
//        for (String str : ans2) {
//            System.out.println(str);
//        }
//        System.out.println("=================");

    }
}
